Field of the Invention
This invention relates to systems and methods for implementing a low density parity check (LDPC) decoding algorithm.
Background of the Invention
A binary low-density parity-check (LDPC) code is a binary linear block code with a parity-check matrix that has a low density of 1 s. This property makes it convenient to represent an LDPC code described by parity-check matrix H with a bipartite graph, called a Tanner Graph. The two types of nodes in a Tanner graph are the variable nodes (VNs) and the check nodes (CNs). The variable nodes are also known as bit nodes or left nodes, and the check nodes are also known as constraint nodes or right nodes. Every variable node (or check node) corresponds to a column (or row) of the parity-check matrix H. V={v1, . . . , vn} denotes the set of variable nodes, and by C={c1, . . . , cm} the set of check nodes. Each row is indexed by ={1, . . . , m} and each column of H by I={1, . . . , n}. In this application, both the notation CN i and VN j and the notation CN ci and VN vj are used herein, depending on the context. In the Tanner graph, VN vi is connected to CN cj via an edge if Hj;i=1, and the set of edges on the Tanner graph is denoted by set E.
The systems and methods disclosed herein provide an improved approach for performing LDPC decoding using Tanner graphs.